package com.guang.guiji.rand;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

// 从n个数种随即选取m个（m　<　ｎ）
public class GenerateRand {
	private static Random bigRandom = new Random();// 一个远大于n的随机数

	// 使用概率算法
	public static void generateRandFirst(int a[], int n, int m) {
		int select = m;
		int remaining = n;
		int count = 0;
		for (int i = 0; i < n; i++) {
			if ((bigRandom.nextInt(n * 10 + m * 10) % remaining) < select) {
				a[count++] = i;
				select--;
			}
			remaining--;
		}
	}

	// 使用集合set的元素互异
	public static void generateRandSecond(int a[], int n, int m) {
		Set<Integer> sets = new HashSet<Integer>();
		Random rand = new Random();
		while (sets.size() < m) {
			sets.add(rand.nextInt(n));
		}
	}

	public static void generateRandThird(int a[], int n, int m) {
		int i = 0;
		int[] b = new int[n];
		Random rand = new Random();
		for (i = 0; i < n; i++) {
			b[i] = i;
		}
		for (i = 0; i < m; i++) {
			int randInt = rand.nextInt(n - i) + i;
			int temp;
			if (randInt != i) {
				temp = b[randInt];
				b[randInt] = i;
				b[i] = temp;
			}
		}
		Arrays.sort(b, 0, m);
		a = Arrays.copyOf(b, m);
		// for (i = 0; i < a.length; i++) {
		// System.out.println(a[i]);
		// }
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long startTime = System.currentTimeMillis();// 程序开始行时间

		int n = 10000000;
		int m = 500000;
		int[] a = new int[m];
		generateRandFirst(a, n, m);
		// generateRandSecond(a, n, m);
		// generateRandThird(a, n, m);

		long endTime = System.currentTimeMillis();// 程序结束时间
		System.out.println((endTime - startTime) + "ms");

	}

}
